package com.bluebridgecup.BasicAlgorithms.API2;

import java.math.BigInteger;
import java.util.Scanner;

public class BigInteger求逆元 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int q = scan.nextInt();
        while (q-- > 0) {
            BigInteger a = new BigInteger(scan.next());
            BigInteger b = new BigInteger(scan.next());
            // 计算a模b的逆元
            System.out.println(a.modInverse(b));
        }
        scan.close();
    }
}
